package buckets.strategies;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

import buckets.core.BucketsInstance;
import buckets.core.BucketState;

/**
 * This is a simple heuristic which picks locally optimal choice at each stage
 * while hoping for globally optimal solution.
 *  
 * @author vasek
 *
 */
public final class GreedyAlgorithm extends SearchSpaceSupport implements BucketFillingProblemStrategy {

	private PriorityQueue<BucketState> pq;
	private List<BucketState> closed = new ArrayList<BucketState>();
	
	/**
	 * Constructor.
	 * 
	 * @param instance which is being solved
	 */
	public GreedyAlgorithm(final BucketsInstance instance) {
		super(instance);
		final BucketState target = new BucketState(instance.getTargetCapacities());
		final Comparator<BucketState> comparator = new SimilarityComparator(target); 
		pq = new PriorityQueue<BucketState>(10, comparator); 
	}
	
	@Override
	public void run() {
		pq.offer(new BucketState(instance.getOriginalCapacities()));
		
		BucketState current = pq.poll();
		statesCounter++;
		
		while (!isTarget(current)) {			
			final List<BucketState> neighbors = expand(current);			
			for (BucketState state : neighbors) {
				if (!closed.contains(state) && !pq.contains(state) && !current.equals(state)) {
					pq.offer(state);
					state.setPredecessor(current);
				}				
			}
			
			if (!closed.contains(current)) {
				closed.add(current);
			}
			
			current = pq.poll();
			statesCounter++;
		}
		
		path = (LinkedList<BucketState>) backtrackToStart(current); 	
	}

	@Override
	public List<BucketState> getResultPath() {
		if (path.isEmpty()) {
			run();
		}
		
		return path;
	}

	@Override
	public int getNumberOfPassedStates() {
		return statesCounter;
	}
	
	/**
	 * Similarity comparator. It compares two sequence of buckets with target sequence - less differences
	 * means less similar state.
	 * 
	 * @author vasek
	 *
	 */
	private class SimilarityComparator implements Comparator<BucketState> {
		
		private BucketState target;
		
		/**
		 * Constructor.
		 * 
		 * @param target target state
		 */
		public SimilarityComparator(final BucketState target) {
			super();
			this.target = target;
		}

		@Override
		public int compare(final BucketState state1, final BucketState state2) {			
			final int similarity1 = computeSimilarity(state1); 
			final int similarity2 = computeSimilarity(state2);
			
			if (similarity1 < similarity2) {
				return 1;
			} else {
				return -1;
			}
		}	
		
		/**
		 * Computes similarity, of state regarding target state.
		 * 
		 * @param state which is being investigated for similarity
		 * @return number of positions that match to target vector
		 */
		private int computeSimilarity(final BucketState state) {
			int matches = 0;
			
			for (int i = 0; i < instance.getNumberOfBuckets(); i++) {
				if (state.getConfiguration()[i] == target.getConfiguration()[i]) {
					matches++;
				}
			}
			
			return matches;
		}
	}
}
